This section is intended to provide a background or context to the invention that is recited in the claims. The description herein may include concepts that could be pursued, but are not necessarily ones that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, what is described in this section is not prior art to the description and claims in this application and is not admitted to be prior art by inclusion in this section.
An ad hoc network may be defined as a kind of wireless network where stations or devices communicate directly with other stations or devices and not via an access point. Ad hoc networks are commonly used to establish a network where network infrastructure does not exist.
The promiscuous nature of a wireless network or “the air interface” has been typically considered a hindrance to transmission. Overhearing the other participants' traffic in a wireless communication network is assumed to be interference, which is commonly sought to be remedied. Only recently has it been considered to use the fundamental broadcast characteristic of the air interface to the advantage of a communication network.
Ad hoc networks, where wireless nodes are within range of each other and use each other to relay messages where leveraging the broadcast nature of the air interface, may be beneficial. However, typical ad hoc routing protocols are generally directed to discovering one good route for the life of a connection rather than making use of a diversity of transmission paths available at any instant.
The conditions in an ad hoc network consistently evolve. Discovering a good transmission route is a difficult task in a highly dynamic system. For example, fading alters the condition of each wireless link, making some nodes disappear at a moment's notice, only to reappear soon after. Mobility of the nodes also perturbs the connectivity between node pairs. Accordingly, a good route often ends up being a route that lasts for a desired period of time, no matter how sub-optimal the connection is at any given time.
Some known systems take advantage of the broadcast nature of the air interface. For example, cellular networks schedule packets from a base station to mobile terminals by considering some channel quality indicator (CQI), so that at every time slot, the best channel, with respect to some metric, is chosen. However, this architecture is too specific to cellular architectures to be applied in ad hoc networks.
Notwithstanding the above, opportunistic protocols are beneficial for several reasons. For example, it is helpful to consider the simple case of a square area. To establish a connection between two nodes that sit at some diagonally opposite corners, which are denoted s and d, the nodes are connected via relays, which are uniformly distributed in the square. The connectivity between each node pair is affected by some fading. There are two broad types of routing protocols which are referred to as reactive and proactive. A proactive protocol will try to identify the connectivity between the nodes ahead of time and store the information in a route table. A reactive protocol attempts to identify the route only at the time of the connection establishment.
In a system having static nodes where a single connection is to be established, both proactive and reactive protocols behave similarly. The protocols attempt to identify a route that will last the length of the connection. If the route evolves during the time of the connection, both types of protocols react differently.
In a static environment, where connectivity is perturbed only by fading between two fixed points, the performance of these protocols depends on how robust a route is. Experimental results by implementing and deploying an ad hoc network have shown that most protocols perform poorly. For instance, Douglas S. J. De Couto, Daniel Aguayo, John Bicket, Robert Morris, A High-Throughput Path Metric for Multi-Hop Wireless Routing, Proceedings of the 9th ACM International Conference on Mobile Computing and Networking (MobiCom '03), San Diego, Calif., September 2003 (incorporated herein by reference), shows that existing ad hoc protocols do not perform well where connectivity is perturbed only by fading between two fixed points.
FIG. 1 illustrates the results of a simulation for an ad hoc network using a known routing protocol with a correlated Rayleigh fading. Correlated Gaussian processes were used to generate a correlated fading distribution, which were then used to establish the connectivity between nodes in the square. The connectivity was assumed constant over each time slot. This means that the coherence time of the channel is larger than one time slot. As most ad hoc protocols attempt to take the path with the shortest number of hops, the shortest path length in each time slot is plotted in FIG. 1. For the simulation, a 500 m×500 m square was considered, occupied by a number of nodes varying from 50 to a 100 nodes. The distance at which two nodes can connect was also variable, and depended on the model. The maximum connection distance was set to about 300 m.
The same scenario was simulated for channels described by a Gilbert-Elliot model, as discussed in E. Gilbert, Capacity of a burst-noise channel, Bell System Technical Journal, pp. 1253-65, 1960 (incorporated herein by reference). The Gilbert-Elliot (GE) model is a typical model for simulating a channel with some correlated packet errors. The parameters for the GE model were obtained from Ben Miler, Alastair James, An Analysis of Packet Loss Models for Distributed Speech Recognition in Proc. ICSLP 2004, October 2004 (incorporated herein by reference). Miler gives parameters for three types of channel, each separated by 3 dB. A free space attenuation of the signal was considered to map these types of channel to a distance in the graph of FIG. 1, so that a doubling of the distance corresponds to a 6 dB drop in power. For nodes outside the last range, it was assumed that there was no connectivity. Extending the connectivity range to include these nodes would only increase the variability in the shortest path length. The resulting simulations are plotted as shown in FIG. 2.
It should be noted that interference was not considered in either the GE or the Rayleigh model. Interference would only increase the number of hops as each link would get a higher chance of dropping the packet. This too would increase the variability in the shortest path length. In both cases, it can be seen that the shortest path is subject to some significant variations, even though it is a static network. Most current ad hoc protocols settle on a single route, the shortest path at the time of establishment for a reactive protocol, or the shortest path at the time of compilation of the route table, for a proactive one. Both prove harmful to the performance of the system because either the protocol settles for a shortest path that is not sustainable, or it settles for a path that is under-performing every time there exists a shorter path.
Current ad hoc network systems have not fully harnessed the advantages of opportunistic routing. Opportunistic scheduling has been extensively used in one-to-many transmissions, mostly in scheduling nodes with respect to the conditions of the channel which connects them to a base station. However, in the ad hoc context, there are relevant works to consider which take advantage of the diversity offered by multiple users over the air interface.
The most relevant work on the topic is Sanjit Biswas, Robert Morris, Opportunistic Routing in Multi-Hop Wireless Networks, Proceedings of the Second Workshop on Hot Topics in Networking (HotNets-II), Cambridge, Mass., November 2003 (incorporated herein by reference). This work by Biswas and Morris arose from a practical problem. The RoofNet project (as discussed at http://www.pdos.lcs.mit.edu/roofnet/, incorporated herein by reference) was first deployed using traditional and standardized Media Access Control (MAC) layers and network and routing protocols. However, these protocols turned out to perform somewhat poorly, as discussed in Douglas S. J. De Couto, Daniel Aguayo, John Bicket, Robert Morris, A High-Throughput Path Metric for Multi-Hop Wireless Routing, Proceedings of the 9th ACM International Conference on Mobile Computing and Networking (MobiCom '03), San Diego, Calif., September 2003 (incorporated herein by reference).
To improve the overall performance of the network, the first intuition in Douglas was to change the performance metrics because typical routing protocols choose route based on minimizing a metric, hop count, which leads to under-performing routes. Douglas explored how minimizing the number of retransmission instead of the number of hops would improve the performance.
In a parallel effort, others in the RoofNet group considered opportunistic routing. The idea is to use diversity from one sender to multiple receiver. To achieve this, they modified two key elements: the routing and the MAC protocol. The routing protocol is modified so that there is not one single candidate for the next hop, but rather a list of possible candidates: all the nodes that would forward the packet closer to the destination (in the network topology sense) are included in the routing table.
The MAC is adapted to allow for different receivers to receive the same packet. Thus, the list of intended receivers for the next hop is included in the MAC header. The intended receivers acknowledge in turn, so that the sender knows that at least one receiver has received the packet successfully. All receivers are also assumed to overhear the acknowledgement to decide whether or not to forward their copy of the packet. Unfortunately, the protocol discussed in Biswas was not configured to operate in a dynamic ad hoc network.
FIG. 4 illustrates how the forwarding candidates are ordered in Biswas. Candidate A is a preferred relay over B, and B over C. The acknowledgement is returned to the sender with the most preferred candidate.
Other related work includes GPSR, as discussed in Brad Karp, H. T. Kung, GPSR: Greedy Perimeter Stateless Routing for Wireless Networks in Proc. of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000) (incorporated herein by reference). GPSR is a geographic routing protocol, so it is tangentially related to opportunistic routing. The idea behind GPSR is to forward the packet to the node within range which will then advance the packet the closest to its destination. The advantage to this method, is that there is no scalability issue in the routing table, because determining which node is the next hop is a purely geometric calculation. GPSR, forwarding switches to a perimeter mode when there is no node which is closer to the destination than the current node.
The system described by Brian Blum, Tian He, Sang Son, and John Stankovic. IGF: A state-free robust communication protocol for wireless sensor networks. Technical report CS-2003-11, University of Virginia CS Department, 2003 (incorporated herein by reference), is similar to Biswas in the way that the MAC layer is adapted. node sends a request to a group of potential relays, and the responses to the request are staggered so as to avoid collision. Further, the group of potential relays are composed of nodes which overhear each other, so that an acknowledgement by one of the nodes of the request, is heard by the other nodes. As such, only one node replies, namely the first one to do so. The Blum system differs from Biswas in that the list of potential relays is not given by the sender in the MAC header, but is defined based on the position of the nodes within a geographical area. The area can be mapped using GPS information for position, or some localization algorithm. However, one disadvantage of geographic routing is it requires positioning information and geographic addressing.
Accordingly, there is a need for a routing protocol which adapts itself opportunistically to the channel conditions in a dynamic ad hoc network.